package com.example.sortingalgorithm;

// 插入排序算法
public class InsertionSort {

    /**
     * 插入排序
     * 算法原理：
     * 有一个待排序序列如下：
     * [3, 7, 5, 1, 4]
     * 首先把该序列中的第一个元素看作是一个有序的序列（下面用小括号来表示有序序列）
     * [(3), 7, 5, 1, 4] —— 现在无序序列变成了[7, 5, 1, 4]
     * 然后把该序列的第二个元素抽出，插入到有序序列的合适位置，保证有序序列依旧有序： （这是第一趟插入排序）
     * [(3, 7), 5, 1, 4] —— 现在无序序列变成了[5, 1, 4]
     * 接着把该序列的第三个元素抽出，插入到有序序列的合适位置，确保有序序列依旧有序：（这是第二趟插入排序）
     * [(3, 5, 7), 1, 4] —— 现在无序序列变成了[1, 4]
     * 依次类推，直到无序序列为空
     * 总结：对于一个长度为n的无序序列，需要进行n-1趟插入排序
     * @param array
     * @param <T>
     */
    public static <T extends Comparable> void sort(T[] array){

        // 临时存放从无序序列中抽出的元素
        T currentElement = null;

        // current表示当前要从无序序列中抽出从元素的下标
        for(int current = 1; current <= array.length-1; current++){
            currentElement = array[current];

            // cursor指向需要和当前元素（也就是刚刚从无序序列中抽出的元素）进行比较的元素
            for(int cursor = current-1; cursor >= 0; cursor--){
                // 如果currentElement的值小于cursor所指向元素的值
                // 那么把cursor所指向的元素往后挪
                if(currentElement.compareTo(array[cursor]) < 0){
                    array[cursor+1] = array[cursor];
                    if(cursor == 0){
                        // 如果cursor所指向元素已经是有序序列的首元素
                        // 那么将它往后挪之后应该把currentElement放到cursor的位置
                        array[cursor] = currentElement;
                        break;
                    }
                    continue;
                }else {
                    array[cursor+1] = currentElement;
                    break;
                }
            }
        }
    }
}
